import java.awt.Color;
import java.awt.event.ActionEvent;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.util.Arrays;
import java.util.Vector;

import javax.swing.BorderFactory;
import javax.swing.JButton;

import acm.gui.IntField;
import acm.gui.TableLayout;
import acm.gui.TablePanel;
import acm.program.Program;

public class Sudoku extends Program {

	// the model of the game board
	IntField[][] board;

	/**
	 * Construct a new game of Sudoku.
	 *
	 * Initializes the game board with all zeroes.
	 */
	public Sudoku() {
		super();
		board = new IntField[9][9];
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				board[i][j] = new IntField(0);
			}
		}
	}

	/**
	 * Initialize a new game of Sudoku with a given configuration.
	 *
	 * @param values
	 *            The configuration of the game board.
	 */
	public Sudoku(int[][] values) {
		this();
		setConfiguration(values);
	}

	/**
	 * Initialize the view component.
	 */
	@Override
	public void init() {
		setTitle("Sudoku");
		setLayout(new TableLayout(4, 3));
		for (int i = 0; i < 9; i++) {
			add(assembleInnerTable(i));
		}
		add(new JButton("Solve"));
		addActionListeners();
	}

	/**
	 * Assemble a single 3x3 field.
	 *
	 * @param n
	 *            The number of the 3x3 field to assemble a table component for.
	 * @return The TablePanel containing a 3x3 field.
	 */
	private TablePanel assembleInnerTable(int n) {
		TablePanel tp = new TablePanel(3, 3);
		for (int i = 0; i < 9; i++) {
			// we assemble 3x3 field-wise and have to adjust array indices
			// accordingly
			int row = 3 * (n / 3) + i / 3;
			int col = 3 * (n % 3) + i % 3;

			// The constructor made sure these are instantiated IntFields
			IntField intField = board[row][col];

			// Register a KeyListener to suppress non-digit entries
			intField.addKeyListener(new KeyListener() {
				@Override
				public void keyPressed(KeyEvent e) {
					// don't care
				}

				@Override
				public void keyReleased(KeyEvent e) {
					// don't care
				}

				@Override
				public void keyTyped(KeyEvent e) {
					try {
						// try to parse the pressed keys value into an Integer
						Integer.parseInt(String.valueOf(e.getKeyChar()));
					} catch (NumberFormatException nfe) {
						// consume the event and stop it from propagating
						e.consume();
					}
				}
			});
			tp.add(intField);
		}
		// draw a solid black border around every 3x3 field
		tp.setBorder(BorderFactory.createLineBorder(Color.black));
		return tp;
	}

	/**
	 * Initialize the game board with the given arrays of ints.
	 *
	 * @param init The 9x9 two-dimensional array with int values from 0..9
	 */
	public void setConfiguration(int[][] init) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (init[i][j] > 0 && init[i][j] <= 9) {
					board[i][j].setValue(init[i][j]);
				} else {
					board[i][j].setValue(0);
				}
			}
		}
	}

	/**
	 * Return the current configuration of the game board.
	 *
	 * @return The current configuration.
	 */
	public int[][] getConfiguration() {
		int[][] tmp = new int[9][9];
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				tmp[i][j] = board[i][j].getValue();
			}
		}
		return tmp;
	}

	// if no solution was found, color every field red
	public void colorForFailure() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				board[i][j].setBackground(new Color(255, 0, 0));
			}
		}
	}

	// if there was a solution, color the new values fields green
	public void colorForSuccess(int[][] solution) {
		int[][] actual = getConfiguration();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (solution[i][j] != actual[i][j]) {
					board[i][j].setBackground(new Color(0, 255, 0));
					board[i][j].setValue(solution[i][j]);
				} else {
					board[i][j].setBackground(new Color(255, 255, 255));
				}
			}
		}
	}

	/**
	 * The ActionListeners method to process pressed buttons.
	 */
	@Override
	public void actionPerformed(ActionEvent e) {
		if (e.getActionCommand().equals("Solve")) {
			// The solve button was pressed, find a solution
			int[][] solution = solve(getConfiguration());
			if (solution != null) {
				colorForSuccess(solution);
			} else {
				colorForFailure();
			}
		}
	}

	/**
	 * Solve the given Sudoku configuration and return the result.
	 *
	 * @param configuration A 9x9 two-dimensional array, columns first.
	 * @return The solution for this game of Sudoku.
	 */
	public int[][] solve(int[][] configuration) {
		solve(configuration, 0);		
		return new int[9][9];
	}

	public static void main(final String[] args) {
		final int[][] emptyField = new int[][] { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

		final int[][] fullField = new int[][] { { 5, 3, 4, 6, 7, 8, 9, 1, 2 },
				{ 6, 7, 2, 1, 9, 5, 3, 4, 8 }, { 1, 9, 8, 3, 4, 2, 5, 6, 7 },
				{ 8, 5, 9, 7, 6, 1, 4, 2, 3 }, { 4, 2, 6, 8, 5, 3, 7, 9, 1 },
				{ 7, 1, 3, 9, 2, 4, 8, 5, 6 }, { 9, 6, 1, 5, 3, 7, 2, 8, 4 },
				{ 2, 8, 7, 4, 1, 9, 6, 3, 5 }, { 3, 4, 5, 2, 8, 6, 1, 7, 9 } };

		final int[][] actualField1 = new int[][] {
				{ 5, 3, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
				{ 0, 9, 8, 0, 0, 0, 0, 6, 0 }, { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
				{ 4, 0, 0, 8, 0, 3, 0, 0, 1 }, { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
				{ 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
				{ 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

		final int[][] actualField2 = new int[][] {
				{ 1, 0, 2, 0, 0, 0, 0, 0, 0 }, { 0, 0, 3, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 4 }, { 0, 4, 0, 0, 5, 0, 0, 0, 0 },
				{ 0, 6, 0, 0, 7, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 2, 0 },
				{ 0, 8, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 8, 0, 0 } };

		new Sudoku(actualField1).start();
	}
	
	/**
	 * Checks if a given field is in a valid state
	 * @param field
	 * @return true if the field is NOT valid - False if it is
	 */
	public boolean reject(int field[][])
	{		
		boolean result = false;
		boolean valid_3x3 = valid_small_field(field);
		boolean valid_9x9 = valid_total_field(field);
		result = (valid_3x3 && valid_9x9);
		return !result; 
	}
	
	/**
	 * Checks if the 3x3 field is valid
	 * @param field
	 * @return boolean
	 */
	private boolean valid_small_field(int field[][])
	{
		boolean valid = true;
		boolean field1 = field_checker(0,0,field);
		boolean field2 = field_checker(0,3,field);
		boolean field3 = field_checker(0,6,field);
		boolean field4 = field_checker(3,0,field);
		boolean field5 = field_checker(3,3,field);
		boolean field6 = field_checker(3,6,field);
		boolean field7 = field_checker(6,0,field);
		boolean field8 = field_checker(6,3,field);
		boolean field9 = field_checker(6,6,field);
		
		valid = field1 && field2 && field3 && field4 && field5 && field6 &&field7 && field8 && field9; 

		return valid;
	}
	
	/**
	 * Checks if a 3x3 field is valid starting at the offset [start_x][start_y]
	 * @param start_x
	 * @param start_y
	 * @param field
	 * @return boolean 
	 */
	private boolean field_checker(int start_x, int start_y, int field[][])
	{
		int value;
		Vector<Integer> observedValues = new Vector<Integer>();
		for(int x = start_x; x < (start_x +3); x++)
		{
			observedValues.clear();
		    //check horizontal
			for(int i = start_y ; i < (start_y+3); i++)
			{
				value = field[x][i];
				if(value != 0)
				{
					if(!observedValues.contains(value))
					{
						observedValues.add(value);
					}
					else
					{
						return false;
					}
				}				
			}
			
			observedValues.clear();
			//check vertical
			for(int j = start_y ; j < (start_y+3); j++)
			{
				value = field[j][x];
				if(value != 0)
				{
					if(!observedValues.contains(value))
					{
						observedValues.add(value);
					}
					else
					{
						return false;
					}
				}
			}
		}
		return true;
	}
	
	/**
	 * checks if the 9x9 field is valid
	 * @param field
	 * @return boolean 
	 */
	private boolean valid_total_field(int field[][])
	{
		int value;
		Vector<Integer> observedValues = new Vector<Integer>();
		for(int row = 0; row < 9; row++)
		{
			observedValues.clear();
		    //check horizontal
			for(int i = 0 ; i < 9; i++)
			{
				value = field[row][i];
				if(value != 0)
				{
					if(!observedValues.contains(value))
					{
						observedValues.add(value);
					}
					else
					{
						return false;
					}
				}				
			}
			observedValues.clear();
			//check vertical
			for(int j = 0 ; j < 9; j++)
			{
				value = field[j][row];
				if(value != 0)
				{
					if(!observedValues.contains(value))
					{
						observedValues.add(value);
					}
					else
					{
						return false;
					}
				}
			}
		}
		return true;
	}
	
	/**
	 * getNextFreeField takes a configuration and returns the position of the next free field.
	 * @param field
	 * @return Integer with the position of the field (divide by 9 to get row, remainder is the column), if no free field returns -1
	 */
	public int getNextFreeField(int field[][])
	{
		int row, column;
		for (row = 0; row < 9; row++)
		{
			for (column = 0; column < 9; column++)
			{
				if (field[row][column] == 0)
				{
					return (row * 9) + column;
				}
			}
		}
		return -1;
	}
	
	/**
	 * Next Extension gets a Sudoku Matrix and a position and then increments the value on the position. If the 
	 * increment operation results in the value at that position being higher than 9, getNextExtension returns null, otherwise
	 * it returns the changes Sudoku matrix
	 * @param field
	 * @param position
	 * @return Null or a Sudoku Matrix
	 */
	public int[][] getNextExtension(int[][] field, int position)
	{
		field[position/9][position%9] += 1;
		if(field[position/9][position%9] > 9)
		{
			return null;
		}
		return field;
	}

	private int[][] solve(int[][] field, int position)
	{
		int[][] candidate;
		candidate = getNextExtension(field, position);
		solve(candidate, getNextFreeField(candidate));
		
		if (reject(field) || candidate == null)
		{
			return null;
		}
		else if (getNextFreeField(field) == -1)
		{
			return field;
		}
		
		return null;
	}
		
}